package com.ocean.hash;

/**
 * <Description> <br>
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/02/15 <br>
 */
public class MyHashSet {

    public static void main(String[] args) {
        MyHashSet myHashSet = new MyHashSet();
        myHashSet.add(1);      // set = [1]
        myHashSet.add(2);      // set = [1, 2]
        System.out.println(myHashSet.contains(1));
        System.out.println(myHashSet.contains(3));
        myHashSet.add(2);      // set = [1, 2]
        System.out.println(myHashSet.contains(2));
        myHashSet.remove(2);   // set = [1]
        myHashSet.contains(2); // 返回 False ，（已移除）
    }

    /**
     * 散列表默认长度
     */
    private static final int DEFAULT_INITAL_CAPACITY = 8;

    /**
     * 装载因子
     */
    private static final float LOAD_FACTOR = 0.75f;

    /**
     * 初始化散列表数组
     */
    private Entry<Integer, Integer>[] table;

    private int size;
    /**
     * 散列表索引数量
     */
    private int use = 0;


    public MyHashSet() {
        table = new Entry[DEFAULT_INITAL_CAPACITY];
    }

    public void add(int key) {
        int index = hash(key);
        if (table[index] == null) {
            // 创建哨兵节点
            table[index] = new Entry<>(null, null);
        }
        Entry<Integer, Integer> temp = table[index];

        if (temp.next == null) {
            temp.next = new Entry<>(key, null);
            size++;
            use++;
            // 动态扩容
            if (use >= table.length * LOAD_FACTOR) {
                resize();
            }
        } else {
            // 说明该位置已经存在节点信息
            do {
                temp = temp.next;
                if (temp.key == key) {
                    return;
                }
            } while (temp.next != null);
            Entry<Integer, Integer> tmp = table[index].next;
            table[index].next = new Entry<>(key, tmp);
            size++;
        }

    }

    private void resize() {
        Entry<Integer, Integer>[] oldTable = table;
        table = new Entry[table.length * 2];
        use = 0;
        for (int i = 0; i < oldTable.length; i++) {
            if (oldTable[i] == null || oldTable[i].next == null) {
                continue;
            }
            Entry<Integer, Integer> e = oldTable[i];
            while (e.next != null) {
                e = e.next;
                // 重新计算hash
                int newIndex = hash(e.key);
                if (table[newIndex] == null) {
                    use++;
                    table[newIndex] = new Entry<>(null, null);
                }
                // 使用头插法
                table[newIndex].next = new Entry<>(e.key, table[newIndex].next);
            }
        }
    }

    public void remove(int key) {
        int index = hash(key);
        Entry<Integer, Integer> cur = table[index];
        if (cur == null || cur.next == null) {
            return;
        }
        // 遍历链表 移除链表中key相同的
        Entry<Integer, Integer> pre;
        do {
            pre = cur;
            cur = cur.next;
            if (cur.key == key) {
                // 移除
                pre.next = cur.next;
                size--;
                if (table[index].next == null) {
                    use--;
                }
                return;
            }
        } while (cur.next != null);
    }

    public boolean contains(int key) {
        int index = hash(key);
        if (table[index] == null) {
            return false;
        }
        Entry<Integer, Integer> temp = table[index];
        while (temp.next != null) {
            temp = temp.next;
            if (temp.key == key) {
                return true;
            }
        }
        return false;
    }

    private int hash(Object key) {
        int h;
        return (key == null) ? 0 : ((h = key.hashCode()) ^ (h >>> 16)) % table.length;
    }

    private static class Entry<K, V> {
        private K key;
        private Entry<K, V> next;

        public Entry(K key, Entry<K, V> next) {
            this.key = key;
            this.next = next;
        }
    }
}
